题目分析

在做这个题目之前，可以先去做Leetcode 70题或者经典的斐波那契数列，那两个题目是这类最简单的问题，然后再回来思考本题，就可能茅塞顿开。

DP

这种题目是最经典的动态规划问题，和爬楼梯相同，要想爬前n阶楼梯，可以有两种方法，一个是通过n - 1阶爬1阶到n，也可以通过n - 2阶爬2阶到n。因此爬楼梯的状态转移方程是
$$f[i] = \begin{cases} f[i - 1] + f[i - 2] & i \ge 2 \ 1 & i < 2 \end{cases}$$

这个题目相同，只是加了一些限制条件，当计算前n个数字有多少编码方式，可以通过前n - 1个数字的编码方式加上第n个数字的编码方式，也可以通过前n - 2个数字的编码方式加上n - 1和第n两个数字组成的编码方式。

当第n个数字为0时，无法编码，即无法通过前n - 1个数字加上第n个数字的编码方式。
当第n -1和n两个组成的数字小于10或者大于26时，无法编码，即无法通过前n - 2个数字的编码方式加上n - 1和第n个数字组成的编码方式。

用dp[i + 2]数组保存前i个数字的编码方式，并给初始值dp[0]和dp[1]都赋值为1。DP算法的时间复杂度为$O(n)，空间复杂度为$O(n)$

class Solution(object):
    def numDecodings(self, s):
        dp = [1, 1] + [0] * len(s)
        for i in range(2, len(s) + 2):
            if s[i - 2] != '0':
                dp[i] += dp[i - 1]
            if i - 3 >= 0 and 10 <= int(s[i - 3] + s[i - 2]) <= 26:
                dp[i] += dp[i - 2]
        return dp[-1]

优化DP

优化DP思路相同，只是我们不需要使用dp数组存放所有的编码个数，算法只用到了前一个和前两个字符的编码个数，因此我们只需要使用n_2和n_1表示前n - 2个和前n - 1个字符的编码个数。就像斐波那契数列一样使用a和b就可以求出f(n)。优化DP算法的时间复杂度为$O(n)，空间复杂度为$O(1)$

class Solution(object):
    def numDecodings(self, s):
        n_2, n_1 = [1, 1]
        for i in range(2, len(s) + 2):
            tmp = 0
            if s[i - 2] != '0':
                tmp = n_1
            if i - 3 >= 0 and 10 <= int(s[i - 3] + s[i - 2]) <= 26:
                tmp += n_2
            n_2, n_1 = n_1, tmp
        return n_1

刷题总结

这是动态规划题目中最最简单的问题了，笔试基本上不会遇到，面试可能会遇到，如果遇到了就太幸运了。但是如果这个题目做不出来的话，基本上就没后续了，小伙伴们一定要警惕。